package cn.zifangsky.sort;

/**
 * 归并排序
 *
 * @author zifangsky
 * @date 2019/1/7
 * @since 1.0.0
 */
public class MergeSort {

    /**
     * 归并排序
     * <p><b>最坏时间复杂度：</b>O(NlogN)</p>
     * @author zifangsky
     * @date 2019/1/7 11:11
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;
        //临时数组
        int[] tempArray = new int[length];
        
        mergeSort(array, tempArray, 0, (length - 1));

        return array;
    }


    /**
     * 归并排序
     * @param array 待排序数组
     * @param tempArray 临时数组
     * @param startIndex 待排序数据段在数组中的开始索引
     * @param endIndex 待排序数据段在数组中的结束索引
     */
    private static void mergeSort(int[] array, int[] tempArray, int startIndex, int endIndex){
        if(startIndex < endIndex){
            int middle = (startIndex + endIndex) / 2;
            //1. 排序前一半数据段
            mergeSort(array, tempArray, startIndex, middle);
            //2. 排序后一半数据段
            mergeSort(array, tempArray, (middle + 1), endIndex);
            //3. 合并当前数据段
            merge(array, tempArray, startIndex, endIndex);
        }
    }

    /**
     * 合并两个数据段
     */
    private static void merge(int[] array, int[] tempArray, int startIndex, int endIndex){
        int middle = (startIndex + endIndex) / 2;

        //待复制数据段在tempArray数组中的索引
        int index = startIndex;
        int i = startIndex, j = (middle + 1);

        //1. 将数组array的 leftIndex ~ rightIndex 索引处的数据按照顺序复制到数组tempArray的对应位置
        while (i <= middle && j <= endIndex){
            if(array[i] < array[j]){
                tempArray[index] = array[i];
                i++;
            }else{
                tempArray[index] = array[j];
                j++;
            }
            index++;
        }

        //2.1 如果前半部分还有剩下的数据，则直接复制过去
        if(i <= middle && j > endIndex){
            while (i <= middle){
                tempArray[index] = array[i];
                i++;
                index++;
            }
        }
        //2.1 如果后半部分还有剩下的数据，则直接复制过去
        else if(i > middle && j <= endIndex){
            while (j <= endIndex){
                tempArray[index] = array[j];
                j++;
                index++;
            }
        }

        //3. 将tempArray指定数据段复制回array
        for(int k = startIndex; k <= endIndex; k++){
            array[k] = tempArray[k];
        }
    }

}
